The present invention relates in general to communications systems and is particularly directed to an adaptive link assignment scheme for dynamically changing communication node topologies.
In multistation or multinode communication networks it is essential to maintain communication paths between nodes to assure that communication can be had between any node in the network and any other node in the network. This is particularly critical in remote communication networks such as communication satellite networks. While equipment malfunction can result in loss of a communication link, in dynamically positioned networks such as satellite networks, communication links between nodes can also be lost if the two nodes move such that they are no longer in line of sight (LOS).
Generally each node is capable of communication over several communication links, which by way of example might be laser links or radio frequency links, or a combination thereof Thus, for example, a communication satellite might be provided with several antennas permitting it to have simultaneous communication with several other satellites over separate paths. Problems can arise in the assignment of the communication links when there are more LOS neighbors of a node than there are communication ports. In such a situation, a link assignment scheme must be utilized to determine the communication links to be established and maintained. Such a scheme must consider the desired network connectivity, determine schedules for establishing and disconnecting links, and command the establishment and disconnection of links in accordance with those schedules, all by utilizing the communication resources available to the node.
A satellite network might include, for example, 48 satellites. It is desirable that any one of the 48 satellites be able to communicate with any other of the 48 satellites. While a single communication path from any one satellite to any other satellite permits such communication, it is desirable that redundant paths be provided to assure no loss of communication in the event that a link is broken, due to either a failure at a node or a failure in a link. Thus, although the minimum link assignment that can provide the desired communication is a single path between nodes, it is desirable that at least two independent communication paths be provided between any one node and any other node in the network, and it is even more preferable that three paths exist so that communications can be maintained even in the event of breakdown of two communication paths.
Design considerations of communication paths in static networks are discussed in the text Computer Networks, by A. S. Tanenbaum, Prentice Hall, 1981. The paper "A Distributed Link Assignment (Reconstitution) Algorithm for Space-based SDI Networks," by J. B. Cain, S. L. Adams, M. D. Noakes, P. J. Knoke, and E. I. Althouse, published at pages 29.2.2-29.2.7 in the MILCOM '87 Conference Record, October 1987, describes an algorithm for assigning communication links in a dynamic multinode communication network. Additional detail is presented in the Harris Corporation ADNMS Technical Report "Selected Algorithm Description," dated Nov. 5, 1987 and prepared for The Naval Research Laboratory under Contract No. N00014-86-C-2056. The present invention considers key aspects of the matter and presents an improved algorithm.